import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.*;

/**
 * @Name: Main
 * @Description:
 * @Author: Mr.Tong
 */
@Slf4j
public class Main {


    // 将 s[j] 向上拨动⼀次
    String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9')
            ch[j] = '0';
        else
            ch[j] += 1;
        return new String(ch);
    }

    // 将 s[j] 向下拨动⼀次
    String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0')
            ch[j] = '9';
        else
            ch[j] -= 1;
        return new String(ch);
    }


    // BFS 框架，打印出所有可能的密码
    void BFS(String target) {
        // 核心数据结构-队列
        Queue<String> q = new LinkedList<>();
        // 添加根节点
        q.offer("0000");
        while (!q.isEmpty()) {
            int sz = q.size();
            /* 将当前队列中的所有节点向周围扩散 */
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                /* 判断是否到达终点 */
                System.out.println(cur);
                /* 将⼀个节点的相邻节点加⼊队列 */
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    String down = minusOne(cur, j);
                    q.offer(up);
                    q.offer(down);
                }
            }
            // 队列中的数据已经更新完
            /* 在这⾥增加步数 */
        }
        return;
    }


    public int openLock(String[] deadends, String target) {
        // 记录需要跳过的死亡密码
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        // ⽤集合不⽤队列，可以快速判断元素是否存在
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int step = 0;
        q1.add("0000");
        q2.add(target);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            // 哈希集合在遍历的过程中不能修改，⽤ temp 存储扩散结果
            Set<String> temp = new HashSet<>();
            /* 将 q1 中的所有节点向周围扩散 */
            for (String cur : q1) {
                // 不能出现死亡密码
                if (deads.contains(cur))
                    continue;
                /* 判断是否到达终点 */
                if (q2.contains(cur))
                    return step;
                visited.add(cur);
                /* 将⼀个节点的未遍历相邻节点加⼊集合 */
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up))
                        temp.add(up);
                    String down = minusOne(cur, j);
                    if (!visited.contains(down))
                        temp.add(down);
                }
            }
            /* 在这⾥增加步数 */
            step++;
            // 下一轮进行扩散的时候，扩散较少的那个集合
            // 对于temp和q2来说，将最小的那个给q1
            if (temp.size() <= q2.size()) {
                q1 = temp;
            } else {
                q1 = q2;
                q2 = temp;
            }
        }
        return -1;
    }


    @Test
    public void test() {
        int[] ints = {4, 1, 2, 1, 2};
        int i = missingNumber(ints);
        System.out.println(i);


    }


    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            n = n & (n - 1);
            sum++;
        }
        return sum;
    }

    public boolean isPowerOfTwo(int n) {
        return n > 0 && ((n & (n - 1)) == 0);
    }

    public int singleNumber(int[] nums) {
        int res = 0;
        for (int n : nums) {
            res ^= n;
        }
        return res;
    }


    public int missingNumber(int[] nums) {
        // list放置索引和nums中的所有值，后续依次对list中的数据进行异或操作
        ArrayList<Integer> list = new ArrayList<>();
        // 把索引全都加入list
        for (int i = 0; i <= nums.length; i++) {
            list.add(i);
        }
        // 把nums中的值全都加入list
        for (int num : nums) {
            list.add(num);
        }
        // 对list中的所有值进行异或操作
        int result = 0;
        for (Integer integer : list) {
            result ^= integer;
        }
        return result;
    }

    @Test
    public void testName() {
        System.out.println(preimageSizeFZF(5));


    }

    public int preimageSizeFZF(int K) {
        long lo = 0, hi = Long.MAX_VALUE;
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) < K) {
                lo = mid + 1;
            } else if (trailingZeroes(mid) > K) {
                hi = mid;
            } else {
                return 5;
            }
        }
        return 0;
    }

    // 全都改成long类型，避免整型溢出
    public long trailingZeroes(long n) {
        long result = 0;
        long d = 5;
        while (d <= n) {
            result += n / d;
            d *= 5;
        }
        return result;
    }

    public int base = 1337;

    // 递归
    public int superPow(int a, int[] b) {
        // 递归终止条件
        if (b.length == 0) return 1;
        // 将原问题化简，缩小规模递归求解
        // 计算第一部分
        int part1 = recursionPow(a, b[b.length - 1]);
        // 计算第二部分
        int part2 = recursionPow(superPow(a, Arrays.copyOf(b, b.length - 1)), 10);
        // 合并结果
        return (part1) * (part2) % base;
    }


    // 非递归快速幂
    public int recursionPow(int a, int b) {
        if (b < 0) return -1;// 非法情况
        if (b == 0) {// 0
            return 1;// 相当于是递归的结束条件
        } else if (b % 2 == 1) {// 奇数
            return (recursionPow(a, b - 1) * (a % base)) % base;
        } else {// 偶数
            // tmp变量是必要的
            // 如果写成recursionPow(a, b / 2)*recursionPow(a, b / 2)
            // 则计算机会计算两次，那么算法退化成O(N)的时间复杂度
            int tmp = recursionPow(a, b / 2);
            return (tmp * tmp) % base;
        }
    }

    public int unRecursionPow(int a, int n) {
        if (n < 0) return -1;//非法情况
        if (n == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
        int ans = 1;
        a %= base;
        while (n != 0) {
            if ((n & 1) == 1) {//如果n的当前末位为1
                ans *= a;  //ans乘上当前的a
                ans %= base;
            }
            a *= a;        //a自乘
            a %= base;
            n >>= 1;       //n往右移一位
        }
        return ans;
    }

    @Test
    public void testN() {
        int i = unRecursionPow(3, 4);
        System.out.println(i);

    }

    public int myPow(int a, int b) {
        if (b < 0) return -1;//非法情况
        if (b == 0) return 1;
        if (b == 1) return a;
        return a * myPow(a, b - 1);
    }


    @Test
    public void teste() {
        double v = myPow(1.00000, -2147483648);
        System.out.println(v);

    }

    public double myPow(double x, int n) {
        long N = n;
        if (n == 0) return 1;
        return N < 0 ? 1 / unRPow(x, -N) : unRPow(x, N);
    }


    public double unRPow(double x, long n) {
        if (n < 0) return -1;
        if (n == 0) return 1;
        double ans = 1.0;
        while (n != 0) {
            if ((n & 1) == 1) {// 最后一位是1
                ans *= x;
            }
            x *= x;
            n >>= 1;
        }
        return ans;
    }


    @Test
    public void test111() {
//        System.out.println(Arrays.asList(findErrorNums(new int[]{1, 2})));
    }


    public int[] findErrorNums(int[] nums) {
        int length = nums.length;
        int[] res = new int[2];
        // 寻找重复元素
        for (int i = 0; i < length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] >= 0)
                nums[index] *= -1;
            else
                res[0] = index + 1;
        }
        // 寻找缺失的元素
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                res[1] = i + 1;
            }
        }
        return res;
    }


}
